#include <stdio.h>
#include <stdlib.h>

// 元素类型以整型为例
typedef int ElemType_Tree;
// 定义一个数据结构类型：单链表的结点
typedef struct LNode {
    ElemType_Tree data;
    struct LNode *next;
}LNode, *LinkList;

// 初始化一个带头结点的单链表
// LNode* 和 LinkList 等价，前者强调是一个结点，后者强调是一个链表
bool LinkListInitWithHead(LinkList &L) {
    L = (LNode*) malloc(sizeof (LNode));
    L->data = NULL;
    L->next = NULL;
    return true;
}

// 头插法生成一个整数序列，输入`9999`停止插入
LinkList CreateLinkListFromHead(LinkList L) {
    ElemType_Tree e;             // 接收要插入的元素值
    scanf("%d", &e);
    // 当输入的元素值不为`9999`时，则向头部插入该元素
    while (9999 != e) {
        // 为新结点申请空间
        LNode* p = (LNode*) malloc(sizeof (LNode));
        p->data = e;
        p->next = L->next;
        L->next = p;
        // 接收写一个元素
        scanf("%d", &e);
    }
    return L;
}

// 尾插法生成一个整数序列，输入`9999`停止插入
LinkList CreateLinkListFromTail(LinkList L) {
    LNode *s = L;           // 定义一个指针 指向尾部结点
    while (s->next != NULL) {
        s = s->next;
    }

    ElemType_Tree e;             // 接收要插入的元素值
    scanf("%d", &e);
    // 当输入的元素值不为`9999`时，则向尾部插入该元素
    while (9999 != e) {
        // 为新结点申请空间
        LNode* p = (LNode*) malloc(sizeof (LNode));
        p->data = e;
        p->next = s->next;
        s->next = p;
        s = p;              // 尾部插入，让s指向新插入的结点
        // 接收写一个元素
        scanf("%d", &e);
    }
    return L;
}

// 遍历打印单链表
void PrintLinkList(LinkList L) {
    if (L->next == NULL) {
        // 链表判空
        printf("NULL");
    } else {
        // 若下一个结点不为空，则将指针指向下一个结点
        while (L->next != NULL) {
            L = L->next;
            printf(" %d", L->data);
        }
    }
    printf("\n");
}

// 指定结点位置的后插操作（在指定结点后面插入一个新结点）
bool LinkListInsertNextNode(LNode *p, ElemType_Tree e) {
    if (p == NULL) {
        return false;
    }

    LNode *s = (LNode*) malloc(sizeof (LNode));
    // 分配新结点的空间失败
    if (s == NULL) {
        return false;
    }
    // 插入新结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// TODO: 指定结点位置的前插操作（在指定结点前面插入一个新结点）
bool LinkListInsertPriorNode(LinkList L, LNode *p, ElemType_Tree e) {
    /**
     * method 1: 从头结点L开始遍历，找到前驱结点然后进行常规的插入操作。时间复杂度为O(n)。
     * method 2: 偷天换日，新建一个结点，将当前结点移到新结点中，原结点的位置更新为要插入的元素值，插入新结点，变相实现前插操作。时间复杂度为O(1)。
     */
     // 略...
     return false;
}

// 在指定位置插入一个新元素
bool LinkListInsertElemByPos(LinkList L, int pos, ElemType_Tree e) {
    // 判断插入位置合法性
    if (pos < 1) {
        return false;
    }

    LNode *p = L;       // 指向当前指针所在结点
    int i = 0;          // 标记当前指针指向第几个结点
    while(p != NULL && i < pos-1) {
        p = p->next;
        i++;
    }
    // 判断插入位置合法性（是否越界）
    // 此时L指向指定位置的前一个结点
    if (p == NULL) {
        return false;
    }

    // 为新结点申请空间
    return LinkListInsertNextNode(p, e);
}

// 删除指定位置的元素，并返回被删除的元素值
ElemType_Tree LinkListDeleteElemByPos(LinkList L, int pos) {
    // 判断插入位置合法性
    if (pos < 1) {
        return NULL;
    }

    int i = 0;
    while (L != NULL && i < pos -1) {
        L = L->next;
        i++;
    }
    // 判断插入位置合法性（是否越界）
    // 此时L指向指定位置的前一个结点
    if (L == NULL) {
        return NULL;
    }

    // 删除第pos个结点，并释放空间
    LNode *p = L->next;     // 要删除的结点
    ElemType_Tree e = p->data;
    L->next = p->next;
    free(p);
    return e;
}


/**
 * 单链表的实现
 *
 * @return
 */
int main() {
    printf("Hello, LinkList!\n");

    /**
     * 带头结点的链表会比不带头结点的链表操作简单一些。
     * 不带头结点的链表在操作时，需要对第一个元素做特殊处理，单独考虑操作第一个元素的逻辑。
     */
    // 链表初始化
    LinkList L;
    LinkListInitWithHead(L);
    PrintLinkList(L);

    printf("Enter a string of integer numbers (with '9999' to end):\n");
    // 头插法插入一个整数序列
//    L = CreateLinkListFromHead(L);
//    PrintLinkList(L);
    // 尾插法插入一个整数序列
    L = CreateLinkListFromTail(L);
    PrintLinkList(L);

    // 在指定位置插入一个元素
    int pos_insert;
    ElemType_Tree e_insert;
    printf("Enter the position to insert element: ");
    scanf("%d", &pos_insert);
    printf("Enter the value of the element: ");
    scanf("%d", &e_insert);
    if (LinkListInsertElemByPos(L, pos_insert, e_insert)) {
        PrintLinkList(L);
    } else {
        printf("Fail to insert..");
    }

    // 删除指定位置的元素，并返回元素值
//    int pos_delete;
//    printf("Enter the position to delete element: ");
//    scanf("%d", &pos_delete);
//    ElemType_Tree e_delete = LinkListDeleteElemByPos(L, pos_delete);
//    if (e_delete != NULL) {
//        printf("The value of the element deleted: %d\n", e_delete);
//    } else {
//        printf("Fail to delete..\n");
//    }
//    PrintLinkList(L);





    return 0;
}